class Solution {//leetcode494——目标和
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0,n=nums.size();
        for(auto e:nums){
            sum+=e;
        }
        int aim=(sum-target)/2;
        if(aim<0||(sum-target)%2!=0) return 0;
        vector<vector<int>> dp(n+1,vector<int>(aim+1));
        dp[0][0]=1;

        for(int i=1;i<n+1;i++){
            for(int j=0;j<aim+1;j++){
                dp[i][j]+=dp[i-1][j];
                if(j-nums[i-1]>=0) dp[i][j]+=dp[i-1][j-nums[i-1]];
            }
        }

        return dp[n][aim];
    }
};